package com.tgy.algorithm.base._概率问题;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class _蓄水池问题 {


    // 等概率得到 1 到 n 的数
    public static int randomN(int n) {

        return (int)(Math.random() * n) + 1;
    }

    public static void test01() {
        int n = 10;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 1000000000; i++) {
            Integer randNum = randomN(n);
            int count;
            if (!map.containsKey(randNum)) {
                count = 1;
            }else {
                count = map.get(randNum) + 1;
            }
            map.put(randNum,count);
        }

        map.keySet().forEach(key->{
            System.out.println(key + ":" + map.get(key));
        });
    }


    public static List<Integer> getRandomValue(int count, int size) {

        ArrayList<Integer> rets = new ArrayList<>();

        for (int i = 1; i <= count; i++) {

            if (i <= size) {
                rets.add(i);
            }else {
                boolean flag = randomN(i) <= size;
                if (flag) {
                    // 需要加进去,随机挑选一个一个需要删除的数 1/size
                    int removeIndex = randomN(size) - 1;
                    Integer remove = rets.remove(removeIndex);
                    // 把当前的数加入
                    rets.add(i);
                    System.out.println("add:" + i +" remove:" + remove);
                }
            }
        }

        return rets;
    }


    public static void main(String[] args) {
        //  test01();
        List<Integer> integers = getRandomValue(10000, 10);
        System.out.println(integers);
    }
}
